package com.wfm.common;

import java.util.List;

public class ListNode {

    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public static void printListNode(ListNode head) {
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

    public static void addNodeTail(ListNode head, ListNode newNode) {
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
        newNode.next = null;
    }

    public static ListNode generalListNode(int begin,int end,int step) {
        ListNode head = new ListNode(begin);
        for (int i = begin+step; i <= end; i+=step) {
            ListNode.addNodeTail(head,new ListNode(i));
        }
        return head;
    }

    public static ListNode generalListNode(int[] nums) {
        ListNode head = new ListNode(-1);
        for (int num : nums) {
            ListNode.addNodeTail(head, new ListNode(num));
        }
        return head.next;
    }

    /**
     * [head，tail】   取区间中的中间，偶数靠右
     * 1-2-3-4-5-null    head=2  tail=5  =》 return 4
     * 由于fast指针循环过程中会取到区间5上，所以靠右
     */
    public static ListNode getMid(ListNode head, ListNode tail){
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        return slow;
    }

    /**
     * [head，tail】   取区间中的中间，偶数靠右
     * 1-2-3-4-5-null    head=2  tail=5  =》 return 3
     */
    public static ListNode getCloseRangeMidLeft(ListNode head, ListNode tail){
        ListNode slow = head, fast = head;
        while (fast.next != tail.next&&fast.next.next!=tail.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * [head，tail】   取区间中的中间，偶数靠右
     * 1-2-3-4-5-null    head=2  tail=5  =》 return 4
     */
    public static ListNode getCloseRangeMidRight(ListNode head, ListNode tail){
        ListNode slow = head, fast = head;
        while (fast != tail.next&&fast.next!=tail.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * [head，tail)   取区间中的中间，偶数靠右
     * 1-2-3-4-5-null    head=1  tail=5 等价于 1-2-3-4 取中靠右 =》 return 3
     */
    public static ListNode getRangeMidRight(ListNode head, ListNode tail){
        ListNode slow = head, fast = head;
        while (fast != tail&&fast.next!=tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * [head，tail)   取区间中的中间，偶数靠左
     * 1-2-3-4-5-null    head=2  tail=5 等价于 1-2-3-4 取中靠左 =》 return 2
     */
    public static ListNode getRangeMidLeft(ListNode head, ListNode tail){
        ListNode slow = head, fast = head;
        while (fast.next != tail&&fast.next.next!=tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 奇数个：1-2-3-null   return 2
     * 偶数个：1-2-3-4-null   return 2
     */
    public static ListNode getMidLeft(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    /**
     * 奇数个：1-2-3-null   return 2
     * 偶数个：1-2-3-4-null   return 3
     */
    public static ListNode getMidRight(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 1-2-3-4-5-null   定位一个链表的下标，下标从1开始，比如第2和第4个元素
     */
    public static ListNode get(ListNode head,int index){
        // 写法一： cur指向head，用while
//        ListNode cur = head;
//        while (cur!=null&&--index>0){
//            cur=cur.next;
//        }
//        return cur;

        // 写法二： cur指向head，用for
//        ListNode cur = head;
//        for (int i = 1; i <index&&cur!=null; i++) {
//            cur=cur.next;
//        }
//        return cur;

        // 写法三： cur指向dummy, 用for ,这种用dummy的，就和数组统一起来了
        ListNode dummy = new ListNode();
        dummy.next=head;
        ListNode cur = dummy;
        for (int i = 0; i < index&&cur!=null; i++) {
            cur=cur.next;
        }
        return cur;
    }
}
